package alo.p19;

/**
 * @ClassName LongestPalindromeSubsequence
 * @Description 最长回文子序列（不连续）
 * @Author Fanxc
 * @DATE 2021/3/15 19:07
 * @Version 1.0
 */
public class LongestPalindromeSubsequence {
    int longestPalindromeSubsequence(int[] A,int n){
        int max=1;
        int[][] L=new int[n][n];
        for (int i = 1; i < n; i++) {
            L[i][i]=1;
            if (A[i]==A[i+1]){
                L[i][i+1]=1;
                max=2;
            }else {
                L[i][i+1]=0;
            }
        }
        for (int k = 3; k < n; k++) {
            for (int i = 1; i <= n-k+1; i++) {
                int j=i+k-1;
                if (A[i]==A[j]){
                    L[i][j]=2+L[i=1][j-1];
                    max=k;
                }else {
                    L[i][j]=Math.max(L[i+1][j],L[i][j-1]);
                }
            }
        }
        return max;
    }
}
